// https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/fen-ge-deng-he-zi-ji-0-1bei-bao-wen-ti-e-3yvz/

// 法一：背包问题
// class Solution {
// public:
//     bool canPartition(vector<int>& nums) {
//         int sum = 0;
//         for (int n: nums) {
//             sum += n;
//         }
//         if (sum % 2 == 1) return false;
//         int m = sum / 2;
//         vector<bool> rec(m + 1, false); // 表示能不能装满大小i
//         rec[0] = true;
//         for (int i = 0; i < nums.size(); ++i) {
//             for (int j = m; j >= nums[i]; --j) {
//                 rec[j] = rec[j] | (rec[j - nums[i]]);
//             }
//         }
//         return rec[m];
//     }
// };

// 法二：回溯 TLE
class Solution {
public:
    bool helper(vector<int>& nums, vector<int>& tmp, int start, int k, int tmp_sum) {
        // res.push_back(tmp);
        if (k == tmp_sum) return true;
        for (int i = start; i < nums.size(); ++i) {
            tmp.push_back(nums[i]);
            tmp_sum += nums[i];
            // helper(nums, tmp, start + 1, k, tmp_sum); !!!!i + 1
            if (helper(nums, tmp, i + 1, k, tmp_sum))
                return true; // 注意return，不然里面找到了返回不到最外层的函数
            tmp.pop_back();
            tmp_sum -= nums[i];
        }
        return false;
    }

    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int n: nums) {
            sum += n;
        }
        if (sum % 2 == 1) return false;
        sum = sum / 2;
        vector<int> tmp;
        return helper(nums, tmp, 0, sum, 0);
    }
};